丁增贤: glibc堆探秘系列之fastbin ——下集

点击上方蓝字关注

作者：丁增贤  笔名：林江川  id：ljcnaix   微信名：9527

毕业于电子科技大学信息与软件工程学院，工作刚满1年零3天。本科期间对底层很感兴趣，技能树一路点歪，目前在做安全相关的工作。对二进制漏洞的挖掘、分析和利用有一些实践。

欢迎给Linuxer投稿，获得精美礼品和文章传播机会：在Linuxer上把一个问题说清或者看懂有惊喜

Linuxer今天诞生了第7777位粉丝，他就是网友“拥抱”。请网友“拥抱”与我们联系，我们将赠送您精美礼品一份。

---

4. _int_free函数

我们继续进入_int_free函数。首先获取chunk的size，并进行安全检查。然后，进入一个if分支结构。当chunk的size小于128比特时（32位glibc库为64比特），进入fastbin的处理分支。显然我们的示例走的就是这个分支，所以其余两个分支的执行逻辑我们暂不考虑。

在继续之前，我们需要简单的介绍一下本文的主角——fastbin。我们已经说过，用户调用free函数释放掉的内存并不会马上归还给操作系统。ptmalloc会将这些释放后空闲的chunk，依据它的大小，用单向/双向链表链接起来（和介绍malloc_chunk结构体时，指针域的生命周期对应起来了），这样的一个链表称为一个bin。当用户下一次请求内存的时候，ptmalloc首先在这些bin中寻找合适的chunk，这样可以避免频繁的系统调用，降低内存分配的开销。对于不同大小的chunk，采用不同的管理方式，才能更好的优化性能。因此bin被分为了很多钟，它们对应不同的chunk大小和不同的管理策略。

一般的情况是，程序在运行时会经常需要申请和释放一些较小的内存空间。当分配器合并了相邻的几个小的chunk之后，也许马上就会有另一个小块内存的请求，这样分配器又需要从大的空闲内存中切分出一块，这样无疑是比较低效的，故而，ptmalloc中在分配过程中引入了fast bins，不大于max_fast （默认值为64B）的chunk被释放后，首先会被放到fast bins 中，fast bins中的chunk并不改变它的使用标志P。这样也就无法将它们合并，当需要给用户分配的chunk小于或等于max_fast时，ptmalloc首先会在fast bins中查找相应的空闲块，然后才会去查找bins中的空闲chunk。在某个特定的时候，ptmalloc会遍历fast bins中的chunk，将相邻的空闲chunk进行合并，并将合并后的chunk加入unsorted bin中，然后再将usorted bin里的chunk加入bins中。

——《glibc内存管理ptmalloc2源代码分析》 by 华庭

对于fastbin是什么，上面这段话我觉得讲的很清晰，就直接引用过来了。现在我们回到_int_free函数的分析。

unsigned int idx = fastbin_index(size); // 根据chunk的size获取fasbin的索引

fb = &fastbin (av, idx);           // 根据索引获取当前chunk归属的fastbin链表

mchunkptr old = *fb, old2;

unsigned int old_idx = ~0u;   

fastbin分支首先检查下一chunk的size，然后获取当前chunk的fastbin链表，然后进入fastbin分支的主干逻辑。下面的代码段，显示了简化的fastbin分支主干逻辑。

do {

    if (__builtin_expect (old == p, 0))

    {

        errstr = "double free or corruption (fasttop)";

        goto errout;

    }

    if (have_lock && old != NULL)

        old_idx = fastbin_index(chunksize(old));

    p->fd = old2 = old;

} while ((old = catomic_compare_and_exchange_val_rel (fb, p, old2)) != old2);

首先检查将要释放的chunk块地址和fastbin头部的chunk块地址是否相同，如果相同，就触发double free error。然后将释放的chunk块的fd域指向fastbin头部的chunk块，最后通过一个CAS  loop将fastbin的头指针指向新释放的chunk。

到这里，我们可以解释为什么连续调用两次“free(a)”会触发崩溃，而按照“free(a);free(b);free(a);”的顺序调用程序可以正常执行。因为调用完“free(b);”后fastbin的头部变成变量b所指向的chunk。当再次调用“free(a);”时，fastbin首部的chunk与正在释放的chunk（变量a指向的chunk）不相同，所以就不会触发double free error，程序正常执行。

5. _int_malloc函数

我们继续来看malloc函数的内部实现。malloc函数是__libc_malloc函数的别名，并且实际的内存分配是在_int_malloc函数中实现的，可以看出在实现上和free函数的一致性。我们执行到程序的15行，然后对函数_int_malloc下断点，使用“c”命令继续执行，进入_int_malloc函数内部。_int_malloc的代码很长，有500多行，但是和fastbin相关的只有一点点，简化掉错误处理后的代码如下所示。

if ((unsigned long) (nb) <= (unsigned long) (get_max_fast ()))

{

    idx = fastbin_index (nb);

    mfastbinptr *fb = &fastbin (av, idx);

    mchunkptr pp = *fb;

    do {

        victim = pp;

        if (victim == NULL) break;

    } while ((pp = catomic_compare_and_exchange_val_acq (fb, victim->fd, victim)) != victim);

    if (victim != 0) {

        check_remalloced_chunk (av, victim, nb);

        void *p = chunk2mem (victim);

        alloc_perturb (p, bytes);

        return p;

    }

}

当需要分配的chunk大小在fastbin的范围内，就获取chunk大小对应的fastbin链表，通过一个CAS loop取得一个空闲chunk并修改fastbin的头部指向该chunk的fd域。然后通过chunk2mem宏（类似mem2chunk宏）获取返回给用户的地址。初始化这块内存后返回给用户。如果在fastbin中没有找到空闲chunk，会继续执行，最终从topchunk中分配对应大小的chunk并返回，这部分与本文开头的问题无关就不详细分析了。

6. 解释栗子

int *a = malloc(8);

int *b = malloc(8);

int *c = malloc(8);

free(a);

// free(a);

free(b);

free(a);

printf("1st malloc(8): %p\n", malloc(8));

printf("2nd malloc(8): %p\n", malloc(8));

printf("3rd malloc(8): %p\n", malloc(8));

我们从第14行开始解释。由于我们释放的内存非常小，只有8比特（64位小于120比特，32位小于60比特的内存释放后都会被加入fastbin），所以释放后被加入fastbin链表。执行完三次free调用后，fastbin链表如下图 6-1所示。

图 6‑1调用3次free函数后的fastbin

第一次调用malloc时，从fastbin头部获得chunk a。然后将fastbin头部指向chunk a的fd域，即chunk b，此时的fastbin如下图6-2所示。

图 6‑2调用一次malloc后的fastbin

再次调用malloc时，从fastbin头部可以获得chunk b，并且fastbin的头部会重新指向chunk a。此时的fastbin又回到调用第一次malloc前的状态。这好像构成了一个循环，按照我们的推论，如果程序继续调用malloc函数，无论调用多少次，返回结果只会在chunk a和chunk b之间切换。我们修改程序验证一下：

#include <stdio.h>

#include <stdlib.h>

int main()

{

    int *a = malloc(8);

    int *b = malloc(8);

    int *c = malloc(8);

    printf("1st malloc(8): %p\n", a);

    printf("2nd malloc(8): %p\n", b);

    printf("3rd malloc(8): %p\n", c);

    free(a);

    free(b);

    free(a);

    for(int i = 0; I < 8; i++) {

        printf("[%d] malloc(8): %p\n", i, malloc(8));

    }

}

编译执行后的运行结果如下：

$ ./fastbin_dup

1st malloc(8): 0x55ca5d475010

2nd malloc(8): 0x55ca5d475030

3rd malloc(8): 0x55ca5d475050

[0] malloc(8): 0x55ca5d475010

[1] malloc(8): 0x55ca5d475030

[2] malloc(8): 0x55ca5d475010

[3] malloc(8): 0x55ca5d475030

[4] malloc(8): 0x55ca5d475010

[5] malloc(8): 0x55ca5d475030

[6] malloc(8): 0x55ca5d475010

[7] malloc(8): 0x55ca5d475030

与我们的分析结论一致，Done！

7. 总结

本文通过分析free函数和malloc函数的实现，还原了ptmalloc中fastbin相关的处理流程，解释了一个double free程序的非预期运行结果。涉及到的重要概念有arena、chunk、bin和fastbin，主要涉及的函数包括__libc_free、_int_free和_int_malloc。

8. 参考文献

[1] glibc内存管理ptmalloc2源代码分析，华庭（庄明强）

[2] how2heap，shellphish，https://github.com/shellphish/how2heap

[3] malloc源码分析1~5，free源码分析1~2，conansonic，http://blog.csdn.net/conansonic/

[4] 使用gdb调试glibc，Bean_lee，http://blog.chinaunix.net/uid-24774106-id-3642925.html

往期精彩回顾>>>

...

转发的都是朋友

打赏的都是亲人